package leecode.二分法;

public class 寻找重复数 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int duplicate = solution.findDuplicate(new int[]{1, 3, 4, 2, 2});
        System.out.println(duplicate);
    }

    static class Solution {
        public int findDuplicate(int[] nums) {
            int n = nums.length; // 数组中的数字范围为 1 -> n - 1
            int[] p = new int[n];
            for (int i = 0; i < nums.length; i++) {
                p[nums[i] - 1]++;
                if (p[nums[i] - 1] >= 2) return nums[i]; // 出现重复
            }
            return -1;
        }
    }
}
